Field of the Invention
This invention is related to an apparatus, method, and program that manages the regions of a storage apparatus.
Description of Related Art
Previously, file systems such as, for example, FAT (File Allocation Tables) or NTFS (NT File System) were used as the method to manage data stored in a storage device like a hard disk and so forth.
FIG. 1A is a drawing describing the region allocation for an external storage device such as a hard disk, used in prior art.
For example, as shown in FIG. 1A, by means of an unshown utility program for a disk allocator or other such means, 4 regions, 1 to 4 (191, 192, 193, 194), are allocated in external storage device 306 storage area and each are assigned to some file system. A master boot record 195 with a region management table 195a holding region management data are disposed at the beginning of the regions. FIG. 1A shows an example of region management table 195a that includes the region information 196 for region number 3 with its entries of region number 196a, start position 196b, and region size 196c. Region number 196a holds the region number that identifies the region, and in the example it is number 3. The start position holds information on the starting address of the region, and in the example these contents are omitted. Region size 196c holds the number of allocation units for that region and in this example it is 52.
The disk allocation management for the files in each region is complicated by the allocation methods unique to the file systems assigned to each region. For example, a FAT keeps a link list showing the blocks allocated to each file. And a NTFS keeps information on the start position and number of contiguous blocks for the blocks allocated to each file.
To resolve the problem of allocation management for each of these files systems, for example, the art of a buddy system was proposed, as disclosed in patent reference 1 below. A buddy system partitions the storage area in sizes that are a power of 2 and manages allocation that way. A basic buddy system is employed in the allocation of memory objects in a simple system that does not use a virtual storage method.
FIG. 1B is a drawing describing the allocation principles of the buddy system. FIG. 1B shows an assigned area 490 whose size is 2 to the 3rd power (=8) and a tree configuration 580 associated with that assigned area and a bit map 400 pointing to used areas corresponding to nodes in the tree configuration 580.
The tree configuration 580 models hierarchically the relations between the areas that are successive partitions in two (halving) of the size of assigned area 490 down to a predetermined allocation unit size. When the region level at the level of the allocation unit size is taken to be level 1, as shown in the drawing, the level of the root node is 4.
As shown by the arrow with dotted lines, the root node 480 of the tree configuration 580 corresponds to the total area (level 4 region) of the assigned area 490 before partitioning, and the “8” depicted inside the node corresponds to the size of the corresponding assigned area 490. Also, the numbers in parentheses are level-internal numbers to distinguish areas within the same level.
Node 440 connected to the root node 480 by link 540 and node 441 connected to the root node 480 by link 541 correspond to the area (level 3 region) of the assigned area 490 partitioned in half. The size of each of those regions is the 4 shown in the drawing.
Below node 440 is node 420 with a size of 2 and connected by link 520, and node 421 with a size of 2 and connected by link 521. In the same way, below node 441 is node 422 with a size of 2 and connected by link 522, and node 423 with a size of 2 and connected by link 523. These 4 nodes correspond to level 2 regions.
Below node 420 is node 410 with a size of 1 and connected by link 510, and node 411 with a size of 1 and connected by link 511. In the same way, below node 421 is node 412 with a size of 1 and connected by link 512, and node 413 with a size of 1 and connected by link 513, and below node 422 is node 414 with a size of 1 and connected by link 514, and node 415 with a size of 1 and connected by link 515, and below node 423 is node 416 with a size of 1 and connected by link 516, and node 417 with a size of 1 and connected by link 517. These 8 nodes correspond to level 1 regions. Each of the nodes other than the root node 480 corresponds to a single area that is a half of the area corresponding to its parent node. Thus the sum of the area sizes at each level is equal to the size of the assigned area 490.
The bit map 400 shown in FIG. 1B holds bit values corresponding to each of the nodes in the tree configuration 580, as shown by the arrow with dotted line. The bit values at the bit positions shown by the level internal numbers 409 for level 4 shown by the bit map 400 with the label 408 indicate which of the regions at level 4 are being used. The bit values with the level internal numbers 0 and 1 at level 3 shown with the label 404 indicate which of those regions are being used. In the same way, the bit values with the level internal numbers 0 to 3 at level 2 shown with the label 402 indicate which of those regions in level 2 are being used, and the bit values with the level internal numbers 0 to 7 at level 1 shown with the label 401 indicate which of those regions in level 1 are being used.
As shown by FIG. 1B, a bit “1” is set in the level internal number 0 for level 4, the level internal number 0 for level 3, the level internal number 0 for level 2, and the level internal number 0 for level 1, and indicate that whole area corresponding to that bit position cannot be reused. In other words, because the status shown by the bit “1” in the level internal number 0 at level 1 indicates that the area with size 1 corresponding to node 410 is being used, that indicates that an area with a larger size including that area cannot be used as is.
In accordance to the above noted buddy system, when a file or memory area of a certain size is to be allocated, it is sufficient to search for and allocate an available (empty) area among the areas whose sizes are equal to that requested size or exceed it by power-of-2 difference, and when it is released, it is sufficient to return it to the group of available (empty) areas with that size, and thus the allocation and release of files and memory areas and the related area management is simplified.    Patent Document 1: JP 1995-28693 A